import Foundation

// MARK: 树

/// 树节点
public class TreeNode {
    public var val: Int
    public var left: TreeNode?
    public var right: TreeNode?
    public init(_ val: Int) {
        self.val = val
        self.left = nil
        self.right = nil
    }
}

//extension TreeNode: Equatable {
//    func ==(left: TreeNode?, right: TreeNode?) -> Bool {
//        guard let left = left, right = right else {
//            return false
//        }
//        if left.val == right.val &&
//            left.left == right.left &&
//            left.right == right.right {
//            return true
//        }
//        return false
//    }
//}

// 计算树的最大深度
func maxDepth(root: TreeNode?) -> Int {
    guard let root = root else {
        return 0
    }
    return max(maxDepth(root: root.left), maxDepth(root: root.right)) + 1
}

// 判断一颗二叉树是否为二叉查找树
func isValidBST(root: TreeNode?) -> Bool {
    return _helper(node: root, nil, nil)
}

private func _helper(node: TreeNode?, _ min: Int?, _ max: Int?) -> Bool {
    guard let node = node else {
        return true
    }
    
    // 所有右子节点都必须大于根节点
    if let min = min, node.val <= min {
        return false
    }
    
    // 所有左子节点都必须小于根节点
    if let max = max, node.val >= max {
        return false
    }
    
    return _helper(node: node.left, min, node.val) &&
        _helper(node: node.right, node.val, max)
}

// 前序遍历
func preorderTraversal(root: TreeNode?, res: inout [Int]) {
    guard let root = root else {
        return
    }
    
    res.append(root.val)
    preorderTraversal(root: root.left, res: &res)
    preorderTraversal(root: root.right, res: &res)
}


// 中序遍历
func inorderTraversal(root: TreeNode?, res: inout [Int]) {
    guard let root = root else {
        return
    }
    preorderTraversal(root: root.left, res: &res)
    res.append(root.val)
    preorderTraversal(root: root.right, res: &res)
}

// 后续遍历
func postorderTraversal(root: TreeNode?, res: inout [Int]) {
    guard let root = root else {
        return
    }
    preorderTraversal(root: root.left, res: &res)
    preorderTraversal(root: root.right, res: &res)
    res.append(root.val)
}

// 用栈实现的前序遍历
func preorderTraversal2(root: TreeNode?) -> [Int] {
    var res = [Int]()
    var stack = [TreeNode]()
    var node = root
    
    while !stack.isEmpty || node != nil {
        if node != nil {
            res.append(node!.val)
            stack.append(node!)
            node = node!.left
        } else {
            node = stack.removeLast().right
        }
    }
    
    return res
}


// 用队列来帮助实现树的层级遍历
func levelOrder(root: TreeNode?) -> [[Int]] {
    var res = [[Int]]()
    // 用数组来实现队列
    var queue = [TreeNode]()
    
    if let root = root {
        queue.append(root)
    }
    
    while queue.count > 0 {
        var size = queue.count
        var level = [Int]()
        
        for _ in 0..<size {
            let node = queue.removeFirst()
            
            level.append(node.val)
            if let left = node.left {
                queue.append(left)
            }
            if let right = node.right {
                queue.append(right)
            }
        }
        res.append(level)
    }
    
    return res
}

